#include "list.h"
// 链表数据结构

// 链表
// 节点
// 一条链上有多个节点，每个节点有一个指针指向下一个节点，节点是单向查找

// 基本API

// 创建链表
List* create_list(void) {
    List* list = malloc(sizeof(List));
    list->head = NULL;
    list->size = 0;
    return list;
}

void destroy_list(List* list) {
    if (list->size <= 0)
        return;

    Node* node = list->head;
    Node* prev = node->next;
    while(prev != NULL) {
        free(node);
        node = prev;
        prev = prev->next;
    }
    free(node);
    list->head = NULL;
    list->size = 0;
}

// 清空链表
void clear_list(List* list) {
    if (list->size <= 0)
        return;

    Node* node = list->head;
    while (node != NULL)
    {
        node->ptr = NULL;
        node = node->next;
    }
}

// 创建节点
Node* create_node(void* ptr) {
    Node* node = malloc(sizeof(Node));
    node->ptr = ptr;
    node->next = NULL;
    return node;
}

size_t get_list_len(List* list) {
    return list->size;
}

// 在链表插入节点
bool insert_list_node(List* list, int index, void* ptr) {
    if (index < 0 || index >= list->size)
        return false;

    Node* node = list->head;
    while(index - 1 >= 0) {
        node = node->next;
        index--;
    }
    Node* prev = node->next;
    node->next = prev->next;
    node->ptr = ptr;
    list->size++;
    return true;
}

Node* get_list_node_by_index(List* list, int index) {
    if (index < 0 || index >= list->size)
        return NULL;

    Node* node = list->head;
    while (index -1 >= 0)
    {
        node = node->next;
    }
    return node;
}

int get_list_node_by_value(List* list, void* ptr, compare cmp) {
    int result = -1;
    if (list->size <= 0) 
        return result;

    Node* node = list->head;
    while(node != NULL) {
        if (cmp(node->ptr, ptr) == 0) {
            result++;
            break;
        }
        node = node->next;
    }
    return result;
}

void sort_list(List* list, compare cmp) {
    for(Node* i = list->head; i->next != NULL; i = i->next) {
        for(Node* j = i->next; j != NULL; j = j->next) {
            if (cmp(i->ptr, j->ptr) == 1) {
                void* t = i->ptr;
                i->ptr = j->ptr;
                j->ptr = t;
            }
        }
    }
}

void show_list(List* list, void (*show)(const void* ptr)) {
    Node* node = list->head;
    while(node != NULL) {
        show(node->ptr);
        node = node->next;
    }
}

void show_index(List* list, int index, void (*show)(const void* ptr)) {
    int count = 0;
    Node* node = list->head;
    while (count < index)
    {
        node = node->next;
        index++;
    }
    show(node->ptr);
}

// 在链表查找节点
bool remove_list_tail_node(List* list) {
    bool result = false;
    if (list->size <= 0)
        return result;

    if (list->size == 1) {
        free(list->head);
        list->size--;
        result = true;
        return result;
    }

    Node* tail = list->head;
    while (tail->next->next != NULL)
    {
        tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
    list->size--;
    result = true;
    return result;
}

bool remove_list_head_node(List* list) {
    bool result = false;
    if (list->size == 0)
        return result;

    Node* tmp = list->head;
    list->head = list->head->next;
    free(tmp);
    list->size--;
    return result;
}

// 在链表删除节点
bool delete_list_node_by_index(List* list, int index) {
    bool result = false;
    if (list->size <= 0 || index >= list->size)
        return result;

    if (list->size - 1 == index) {
        return remove_list_tail_node(list);
    }

    Node* prev = list->head;
    int i = 0;
    while(i < index - 1) {
        prev = prev->next;
        i++;
    }
    Node* node = prev->next;
    prev->next = node->next;
    free(node);
    list->size--;
    result = true;
    return result;
}

bool delete_list_node_by_value(List* list, void* ptr, compare cmp) {
    bool result = false;
    if (list->size == 0)
        return result;

    if (cmp(list->head->ptr, ptr) == 0) {
        result = remove_list_head_node(list);
        return result;
    }

    Node* node = list->head;
    while(node->next != NULL) {
        if (cmp(node->ptr, ptr) == 0) {
            Node* t = node->next;
            node->next = t->next;
            free(t);
            list->size--;
            result = true;
            break;
        }
        node = node->next;
    }
    return result;
}

// 在链表头部插入节点
void add_list_head(List* list, void* ptr) {
    Node* new_node = create_node(ptr);
    // new_node->ptr = ptr;
    new_node->next = list->head;
    list->head = new_node;
    list->size = list->size + 1;
}

// 在链表尾部插入节点
void add_list_tail(List* list, void* ptr) {
    Node* new_node = create_node(ptr);
    // new_node->ptr = ptr;
    new_node->next = NULL;
    if (list->size == 0) {
        list->head = new_node;
    } else {
        Node* tmp = list->head;
        while (tmp->next != NULL)
        {
            tmp = tmp->next;
        }
        tmp->next = new_node;
    }
    list->size = list->size + 1;
}
